package org.algorithm.biubiu.wheel_2.链表;

import java.util.HashMap;

public class LRUCache {
    class  ListNode {
        public int key;
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(){};
        public ListNode(int key,int val){
            this.key = key;
            this.val = val;
        }

    }

    HashMap<Integer,ListNode> map;
    private int capacity;
    ListNode head = new ListNode();
    ListNode tail = new ListNode();
    public LRUCache(int capacity) {
        map = new HashMap(capacity);
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        moveToTail(map.get(key));
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if(get(key)!=-1){
            ListNode ele = map.get(key);
            ele.val = value;
            return;
        }
        ListNode node = new ListNode(key,value);
        map.put(key,node);

        if(map.size()>capacity){
            ListNode removed =  head.next;
            head.next = removed.next;
            removed.next.prev = head;
            map.remove(removed.key);
        }
        moveToTail(map.get(key));
    }

    public void moveToTail(ListNode node){
        if(node.prev!=null){
            node.prev.next = node.next;
        }
        if(node.next!=null){
            node.next.prev = node.prev;
        }
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }
}
